#include<iostream>
#include<limits>
#include<vector>

int coin(int* coins,int* coinCount,int amount){
        int maxval=amount+1;
        std::vector<int> cause(amount+1,maxval);//用来记录引起dp[i]变化的硬币面值
        std::vector<int> dp(amount+1,maxval);//定义一个向量包含amount+1个元素且均初始化为maxval
        std::vector<int> count(4);
        for(int p=0;p<4;p++){
                count[p]=coinCount[p];
        }//保留各面值硬币数量
        dp[0]=0;//金额为0为特殊情况
        //递归计算dp[i](i>0)
        for(int i=1;i<=amount;++i){//从1开始计算最小硬币数
                for(int j=0;j<4;++j){//从金额最小的硬币开始循环，计算最小的硬币数
                        if(i>=coins[j]&&coinCount[j]>0){
                                dp[i]=std::min(dp[i],dp[i-coins[j]]+1); //分别比较i-1,i-5,i-10,i-25 得到最小值
                                if(dp[i]==dp[i-coins[j]]+1){
                                        cause[i]=j;}
                        }//是coins[j]引起数量变化 
                        if(cause[i]==cause[i-coins[j]]){
                                coinCount[cause[i]]--;
                        }else{
                                coinCount[cause[i-coins[j]]]=count[cause[i-coins[j]]];}
                }
        }
        if(dp[amount]!=maxval){
                return dp[amount];}
        else{
                return -1;
	}
}
